Inserting an Item at Position i - Educational Content

Insertion requires traversal to the predecessor node, resulting in $O(n)$ complexity.

While traversal allows us to efficiently read all $n$ elements, modification operations like insertion require similar $O(n)$ time complexity because we must first **traverse** to the target location.
Insertion requires finding the node immediately preceding the target position $i$, which is position $i-1$.
We use a pointer $p$ to iterate to the node at index $i-1$. This traversal dictates the overall $O(n)$ time complexity.
After creating the new node ($tmp$), the insertion requires two critical pointer assignments to "splice" the new node into the chain.
**Relink 1 (New to Successor):** The `next` pointer of $tmp$ must point to the successor of $p$ (`p.next`).
**Relink 2 (Predecessor to New):** The `next` pointer of $p$ (`p.next`) must be updated to point to the new node ($tmp$).

Complexity Summary: Insertion at Position $i$

Operation	Time Complexity	Space Complexity
Insertion at $i$	$O(n)$	$O(1)$

The $O(n)$ time is dominated by the mandatory traversal to find the predecessor node at index $i-1$.

Linked List Insertion at Position $i$ (Python)

1class Node:
2    # Reusing Node_Structure: {value, next}
3    def __init__(self, value, next_node=None):
4        self.value = value
5        self.next = next_node
6
7def insert_at_position(head, new_data, i):
8    # Handle insertion at head (i=0)
9    if i == 0:
10        return Node(new_data, head)
11
12    p = head 
13    count = 0
14    # Traverse until p is at position i-1
15    while p is not None and count < i - 1:
16        p = p.next
17        count += 1
18        
19    # Check for invalid index
20    if p is None:
21        print("Error: Index out of bounds.")
22        return head 
23        
24    # 1. Create new node (tmp)
25    tmp = Node(new_data)
26    
27    # 2. Relink 1: tmp.next points to p's original successor
28    tmp.next = p.next 
29    
30    # 3. Relink 2: p.next points to tmp
31    p.next = tmp
32    
33    return head
34
35# Setup list: 10 -> 20 -> 40
36head_ex = Node(10, Node(20, Node(40)))
37
38# Insert 30 at index 2 (i=2, so p stops at index 1: 20)
39head_ex = insert_at_position(head_ex, 30, 2)
40
41# Verification output
42current = head_ex
43output = []
44while current:
45    output.append(str(current.value))
46    current = current.next
47print(" -> ".join(output))

Expected Output

10 -> 20 -> 30 -> 40